 package 二叉树;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;

public class 二叉树{
	public static void main(String[] args) {
		//TreeArray tree = new Tree(10);
		//tree.Init();
		Scanner s = new Scanner(System.in);
		String string = s.nextLine();
		s.close();
		TreeList tree = new TreeList(string);
		tree.Print();
		System.out.println();
		System.out.println();
		tree.PreOrder(tree.getRoot());
		System.out.println();
		tree.InOrder(tree.getRoot());
		System.out.println();
		tree.PostOrder(tree.getRoot());
		System.out.println();

	}
}




//数组版
class TreeArray {

	private char[] data;
	private int index = 0;
	public TreeArray(int n) {
		// TODO Auto-generated constructor stub
		data = new char[n+1];
	}
	public int getL(int index) {
		return data[index+1];
	}
	public int getR(int index) {
		return data[index+2];
	}
	public void setNode(int i,char[] d) {
		if(data[index++] == '#') return;
		this.data[i] = d[index-1];
		setNode(2*i ,d);
		setNode(2*i+1,d);
	}
	public void Init(){
		Scanner s = new Scanner(System.in);
		String string = s.nextLine();
		char[] d = string.toCharArray();
		setNode(1, d);
		s.close();
	}
	public void PrintF(int i) {
		
	}
}




//链表版
class Node{
	private char data = '\0';
	private Node L = null;
	private Node R = null;	
	public Node(char data) {
		// TODO Auto-generated constructor stub
		this.data = data;
	}
	public Node() {
		
	}
	public void newL() {
		L = new Node();
	}
	public void newR() {
		R = new Node();
	}
	public Node getL() {
		return L;
	}
	public Node getR() {
		return R;
	}
	public char getData() {
		return data;
	}
	public void setData(char data) {
		this.data = data;
	}
	public void Print() {
		if(data != '\0') System.out.print(data);
	}
}

class TreeList{
	private int i = 0;
	private Node root;
	public TreeList(String string) {
		// TODO Auto-generated constructor stub
		root = new Node();
		char[] d = string.toCharArray();
		InitTree(root, d);
 	}
	public void InitTree(Node node ,char[] d) {
		//先序拓展序列建立树
		if(i >= d.length || d[i++] == '#') return;
		//短路运算
		node.setData(d[i-1]);
		node.newL();
		node.newR();
		InitTree(node.getL(), d);
		InitTree(node.getR(), d);
	}
	public void PreOrder(Node root) {
		//先序非递归遍历
		Node p = root;
		Stack<Node> stack = new Stack<>();
		while(!stack.isEmpty() || (p != null && p.getData() != '\0')) {
			while(p != null && p.getData() != '\0') {
				p.Print();
				if(p.getR() != null && p.getR().getData() != '\0') {
					stack.push(p);
				}
				p = p.getL();
			}
			if(!stack.isEmpty()) {
				p = stack.pop().getR();
			}
		}
	}
	public void InOrder(Node node) {
		//中序遍历
		if(node == null) return;
		InOrder(node.getL());
		node.Print();
		InOrder(node.getR());
	}
	public void PostOrder(Node node) {
		//后序遍历
		if(node == null) return;
		PostOrder(node.getL());
		PostOrder(node.getR());
		node.Print();
	}
	public void Print() {
		//层次遍历
		Queue<Node> queue = new LinkedList<Node>();
		queue.offer(root);
		while(!queue.isEmpty()) {
			Node node = queue.poll();
			node.Print();
			if(node.getL()!=null)
				queue.offer(node.getL());
			if(node.getR()!=null)
				queue.offer(node.getR());
		}
	}
	public Node getRoot() {
		return root;
	}
}